// 计算等位时间
// 给定一个数组arr长度为n，表示n个服务员，每服务一个客人的时间
// 给定一个正数m，表示有m个人等位，如果你是刚来的人，每个客人都遵循有空位就上的原则
// 请问你需要等多久？
// 假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？
// 谷歌的面试，这个题连考了2个月
// 找不到测试链接，所以用对数器验证

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <climits>

using namespace std;

// 堆模拟
// 验证方法，不是重点
// 如果 m 很大，该方法会超时
// 时间复杂度 O(m * log(n))，额外空间复杂度 O(n)
int waitingTime1(vector<int>& arr, int m) 
{
    // 一个一个对象 int[]
    // [醒来时间，服务一个客人要多久]
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> heap;
    int n = arr.size();
    for (int i = 0; i < n; i++) 
    {
        heap.push({0, arr[i]});
    }
    for (int i = 0; i < m; i++) 
    {
        vector<int> cur = heap.top();
        heap.pop();
        cur[0] += cur[1];
        heap.push(cur);
    }
    return heap.top()[0];
}

// 如果每个服务员工作 time，可以接待几位客人（结束的、开始的客人都算）
int f(vector<int>& arr, int time) 
{
    int ans = 0;
    for (int num : arr) 
    {
        ans += (time / num) + 1;
    }
    return ans;
}

// 二分答案法
// 最优解
// 时间复杂度 O(n * log(min * w))，额外空间复杂度 O(1)
int waitingTime2(vector<int>& arr, int w) 
{
    int mn = INT_MAX;
    for (int x : arr) mn = min(mn, x);

    int ans = 0;
    for (int l = 0, r = mn * w, m; l <= r;) 
    {
        // m 中点，表示一定要让服务员工作的时间！
        m = l + ((r - l) >> 1);
        // 能够给几个客人提供服务
        if (f(arr, m) >= w + 1) 
        {
            ans = m;
            r = m - 1;
        } 
        else l = m + 1;
    }
    return ans;
}

// 生成随机数组
vector<int> randomArray(int n, int v) 
{
    vector<int> arr(n);
    for (int i = 0; i < n; i++) 
    {
        arr[i] = rand() % v + 1;
    }
    return arr;
}

// 对数器测试
int main() 
{
    srand(time(nullptr));
    cout << "测试开始" << endl;
    int N = 50;
    int V = 30;
    int M = 3000;
    int testTime = 20000;
    for (int i = 0; i < testTime; i++) 
    {
        int n = rand() % N + 1;
        vector<int>&& arr = randomArray(n, V);
        int m = rand() % M;
        int ans1 = waitingTime1(arr, m);
        int ans2 = waitingTime2(arr, m);
        if (ans1 != ans2) 
        {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;
    return 0;
}